Low-rank matrix completion is a problem of immense practical importance.Recent works on the subject often use nuclear norm as a convex surrogate of therank function. Despite its solid theoretical foundation, the convex version ofthe problem often fails to work satisfactorily in real-life applications. Realdata often suffer from very few observations, with support not meeting therandom requirements, ubiquitous presence of noise and potentially grosscorruptions, sometimes with these simultaneously occurring. This paper proposes a Proximal Alternating Robust Subspace Minimization(PARSuMi) method to tackle the three problems. The proximal alternating schemeexplicitly exploits the rank constraint on the completed matrix and uses the$\ell_0$ pseudo-norm directly in the corruption recovery step. We show that theproposed method for the non-convex and non-smooth model converges to astationary point. Although it is not guaranteed to find the global optimalsolution, in practice we find that our algorithm can typically arrive at a goodlocal minimizer when it is supplied with a reasonably good starting point basedon convex optimization. Extensive experiments with challenging synthetic andreal data demonstrate that our algorithm succeeds in a much larger range ofpractical problems where convex optimization fails, and it also outperformsvarious state-of-the-art algorithms.
展开▼
